257. 二叉树的所有路径

Similar Question

leading to the advanced question

Solution Tips

方案一: DFS

var binaryTreePaths = function(root) {
    // 感觉这题比较适合深度优先遍历哇, 像 depth 一样传递拼接即可
    const res = [];

    dfs(root, '');

    return res;

   function dfs(node, path) {

        if (node.left) {
            dfs(node.left, `${path}->${node.val}`);
        }
        if (node.right) {
            dfs(node.right, `${path}->${node.val}`);
        }

        if (!node.left && !node.right) {
            res.push((`${path}->${node.val}`).slice(2));
        }
    }
};

方案二: BFS

var binaryTreePaths = function(root) {
    const paths = [];
    if (root === null) {
        return paths;
    }
    const node_queue = [root];
    const path_queue = [root.val.toString()];

    while (node_queue.length) {
        const node = node_queue.shift(); 
        const path = path_queue.shift();

        if (node.left === null && node.right === null) {
            paths.push(path);
        } else {
            if (node.left !== null) {
                node_queue.push(node.left);
                path_queue.push(path + "->" + node.left.val.toString());
            }

            if (node.right !== null) {
                node_queue.push(node.right);
                path_queue.push(path + "->" + node.right.val.toString());
            }
        }
    }
    return paths;
};